#include <functional>
#include <queue>
#include <vector>
using namespace std;

class MedianFinder {
private:
  // 大根堆
  priority_queue<int, vector<int>, less<int>> left;
  // 小根堆
  priority_queue<int, vector<int>, greater<int>> right;

public:
  MedianFinder() {}
  void addNum(int num) {
    // 左侧较小部分
    left.push(num);
    if (left.size() && right.size() && left.top() > right.top()) {
      right.push(left.top());
      left.pop();
    }
    if (left.size() > right.size() + 1) {
      right.push(left.top());
      left.pop();
    }
    if (left.size() + 1 < right.size()) {
      left.push(right.top());
      right.pop();
    }
  }

  double findMedian() {
    if (left.size() > right.size()) {
      return left.top();
    }
    if (left.size() < right.size()) {
      return right.top();
    }
    return (left.top() + right.top()) / 2.0;
  }
};